Branch prediction is one technique used to improve data processor performance. Data processors that use branch prediction techniques make a "guess" each time they receive a branch instruction, act on the guess (an "unresolved branch instruction"), and then determine if the guess was correct by completing the instruction (a "resolved branch instruction"). Such a data processor guesses whether a branch will ultimately be taken and jump to a new instruction address or whether it will "fall through" to the next sequential instruction. Data processors that predict branch instructions gain performance because they can make an accurate guess faster than they can complete the branch instruction. These data processors then need only correct wrong guesses.
Branch prediction techniques increase data processor performance by allowing the data processor to fetch the next instruction or group of instructions as soon as possible. The data processor thereby ensures that it has a continuous stream of instructions to execute at all times. This strategy is known as "instruction prefetching" because the data processor fetches the instruction before it executes the branch instruction that determines the address of the prefetched instruction.
In certain data processing systems, uniform instruction prefetching may be detrimental to the overall performance of the system. Oftentimes a data processor does not contain a prefetched instruction in its internal memory cache. In these cases, the data processor must access an external memory system to fetch the instruction. This operation monopolizes the bus associated with the external memory device and may cause other devices sharing the external memory device to perform certain actions consistent with a system memory coherency protocol ("snoop operations"). Also, the data processor can not request another, presumably correct instruction, until it receives the prior, incorrect instruction. It is advantageous to minimize the number of these operations whenever possible.
Each guessed branch instruction compounds the uncertainty in the selected instruction path, and thus the likelihood of an unnecessary fetch. For instance, a certain branch prediction scheme may predict branches correctly 90% of the time and incorrectly 10% of the time. After three predicted and unresolved branches, there may be only a 73% chance that the data processor is fetching instructions along the correct instruction stream path. Continuing with this example, known data processors treat the first and the third branch prediction guesses equally, either prefetching instructions at the addresses indicated by both branch instructions (or at sequential addresses generated after both instructions) or prefetching no instructions. As described above, each of these two instructions may cause the data processor to access an external memory system via a system bus if the data processor does not contain the particular instruction returned by the branch instruction. All other things being equal, it is less desirable to monopolize the system bus to fetch the third instruction than to fetch the first instruction. However, known data processors do not make this distinction.